package microsoft;

import java.util.HashSet;
import java.util.Set;

/**
 * A string is called balanced when every letter occurring in the string ,
 * appears both in upper-and lowercase .
 * For example , the string "CATattac" is balanced ( 'a', 'c', 't' occur in both cases ) ,
 * but "Madam" is not ( 'd' and 'a' appear only in lowercase ) .
 * Note that the number of occurrences does not matter.
 *
 * Write a function :
 * int solution ( string &S) ;
 * that , given a string S of length N ,
 * returns the length of the shortest balanced fragment of S.
 * If S does not contain any balanced fragments ,the function should return -1.
 *
 * Examples :
 * 1 . Given S = "azABaabza" the function should return 5 . The shortest balanced fragment of S is "ABaab".
 * 2 . Given S = "TacoCat" the function should return -1 . There is no balanced fragment
 * 3 . Given S = "AcZCbaBz" the function should return 8 . The shortest balanced fragment is the whole string
 * 4 . Given S = abcdefghijklmnopqrstuvwxyz" , the function should return -1
 *
 * Assume that:
 * N is an integer within the range [1...200]
 * string S consists only of letters ( a-z and / or A-Z )
 */
public class BalancedString {


    public static void main(String[] args) {
        System.out.println(new BalancedString().solution("azABaabza"));
    }

    /**
     * 暴力求解法.
     */
    public int solution(String S) {
        if (S == null || S.length() < 2) return -1;

        int maxLen = -1;
        for (int i = 0; i < S.length() - 1; i++) {
            for (int j = i+1; j < S.length(); j++) {
                if (isBalancedStr(S, i, j)){
                    maxLen = ((j-i + 1)>maxLen)?(j-i + 1):maxLen;
                }
            }
        }

        return maxLen<=1 ? -1:maxLen;
    }

    /**
     * 判读是否为平衡子串.
     */
    private boolean isBalancedStr(String S, int left, int right) {
        if (right - left < 1) {
            return false;
        }

        Set<Character> set = new HashSet<Character>();
        for (int i = left; i <= right; i++) {
            set.add(S.charAt(i));
        }

        for (Character c : set) {
            if (c >= 'a' && c <= 'z') {
                if (!set.contains(Character.toUpperCase(c))) {
                    return false;
                }
            } else {
                if (!set.contains(Character.toLowerCase(c))) {
                    return false;
                }
            }
        }
        return true;
    }
}
